#![allow(dead_code)]
use std::{cell::RefCell, rc::Rc};

use num::{
    abs,
    bigint::{RandBigInt, ToBigInt},
    integer::gcd,
    BigUint,
};
use num_traits::One;
use rand::distributions::uniform::{self, UniformInt, UniformSampler};

pub fn find_max_prime_factor(number: u128) -> u128 {
    let save = Rc::new(RefCell::new(1));
    let max = max_prime_factor_u128(number, save.clone());
    *save.borrow_mut() = 1; // 千万不要忘记了复位这个临时比较的空间
    max

    // 下面的代码是用没有限制的大整数实现的算法，因为此题要求返回的是u128类型，所以优先使用了上面的u128类型
    // let save = Rc::new(RefCell::new(1u8.into()));
    // let max = max_prime_factor_biguint(number.into(), save.clone());
    // *save.borrow_mut() = 1u8.into();
    // let value = max.to_u64_digits();
    // let len = value.len();

    // if len == 1 {
    //     value[0] as u128
    // } else if len == 2 {
    //     ((value[1] as u128) << 64) | value[0] as u128
    // } else {
    //     0
    // }
}

// -------------------------------------------------------------------------------------------------------------------------------------------------------------------
// ---------------------------------------------------------------------------------------------------------------------------------------------------
/// 这个板块是用u128实现的算法，在算式中，好多地方出现了数据溢出的现象，解决的办法就是先转换成BigUint大整数运行，然后再转换回来。
/// 不过这个版本的实现，速度是真的快，10组数据在8ms所有，比大整数实现的算法快3倍左右。但是大整数实现的版本应用范围更加广，不太担心
/// 数据溢出的现象了。
/// 求整数number的最大素因子,用pollard_rho方法找到因子，然后比较，找到最大的那一个
pub fn max_prime_factor_u128(number: u128, save: Rc<RefCell<u128>>) -> u128 {
    if number == 1 {
        return *save.borrow();
    }

    let fac = pollard_rho_u128(number);

    if fac == 1 || fac == number {
        let max = save.borrow().max(fac);
        *save.borrow_mut() = max;
        return max;
    } else {
        let max = max_prime_factor_u128(fac, save.clone())
            .max(max_prime_factor_u128(number / fac, save.clone()));
        *save.borrow_mut() = max;
    }
    return *save.borrow();
}

// 使用pollard_rho算法求因式
pub fn pollard_rho_u128(number: u128) -> u128 {
    if number == 4 {
        return 2;
    }
    if is_prime_u128(number) {
        return number;
    }

    loop {
        let c = rand_u128(1, number - 1);
        let mut t = 0;
        let mut r = 0;
        let mut p = 1;
        let mut q;
        loop {
            for _ in 0u32..128 {
                t = f_u128(t, c, number);
                r = f_u128(f_u128(r, c, number), c, number);
                if t == r {
                    break;
                }
                q = overflow_handle(p, (t.wrapping_sub(r) as i128).abs() as u128, number);
                if q == 0 {
                    break;
                }
                p = q;
            }

            let d = gcd(p, number);
            if d > 1u8.into() {
                return d;
            }
            if t == r {
                break;
            }
        }
    }
}

#[inline(always)]
fn rand_u128(start: u128, end: u128) -> u128 {
    let mut rng = rand::thread_rng();
    let uni: UniformInt<u128> = uniform::UniformInt::new(start, end);
    uni.sample(&mut rng)
}

#[inline(always)]
fn f_u128(x: u128, c: u128, number: u128) -> u128 {
    (overflow_handle(x, x, number) + c % number) % number
}

// 米勒拉宾素性检验：如果n是一个素数的话，那么n-1可以写成n-1=(a的(2^r)*d次方)*d
// 0<= r <= s-1,a是随机的从[1, n-1]中选取的，如果我们能找到(a^d mod n) != 1 且 (a的(2^r)*d次方) mod n != -1
// 则说明a是n为合数的一个凭证。
// 参数解释:a,d，n分别是公式中的a,d,n
// 这个函数计算出a^d mod n的值。使用快速幂算法。
// 初始化结果为1，基数为a，指数为d。
// 当指数d大于0时，如果d为奇数，则将结果乘以基数并对n取模。
// 将基数平方并对n取模，将指数整除2。
// 重复上述步骤直到指数d为0。
// 返回a^d mod n
fn fast_power_mod_u128(mut a: u128, mut d: u128, n: u128) -> u128 {
    let mut res: u128 = 1;
    while d != 0 {
        if (d & 1) != 0 {
            res = overflow_handle(res, a, n);
        }
        a = overflow_handle(a, a, n);
        d >>= 1;
    }
    res
}

#[inline(always)]
fn overflow_handle(a: u128, b: u128, m: u128) -> u128 {
    if a.checked_mul(b).is_none() {
        let a: BigUint = a.into();
        let b: BigUint = b.into();
        let m: BigUint = m.into();
        let ret = (a * b % m).to_u64_digits();
        let len = ret.len();
        if len == 1 {
            ret[0] as u128
        } else if len == 2 {
            (ret[1] as u128) << 64 | (ret[0] as u128)
        } else {
            0
        }
    } else {
        a * b % m
    }
}

// 使用费马小定理进行快速检测的基数集合
static A: [u128; 7] = [2, 325, 9375, 28178, 450775, 9780504, 1795265022];

/// 米勒拉宾素性检验：如果n是一个素数的话，那么n-1可以写成n-1=(a的(2^r)*d次方)*d
/// 0<= r <= s-1,a是随机的从[1, n-1]中选取的，如果我们能找到(a^d mod n) != 1 且 (a的(2^r)*d次方) mod n != -1
/// 则说明a是n为合数的一个凭证。
/// 参数解释:a,d，n分别是公式中的a,d,n
pub fn is_prime_u128(n: u128) -> bool {
    if n < 3 || &n % 2 == 0 {
        return n == 2;
    }
    // t保存的是s的值
    let mut t = 0;
    let mut d = n - 1;
    while d % 2 == 0 {
        d = d / 2;
        t = t + 1;
    }

    for a in A {
        let mut v = fast_power_mod_u128(a, d, n);
        if v == 1 || v == n - 1 || v == 0 {
            continue;
        }
        let mut i = 1;

        while i <= t {
            v = overflow_handle(v, v, n);
            if v == n - 1 && i != t {
                v = 1; // 不需要再循环了。
                break;
            }
            if v == 1 {
                return false;
            }
            i = i + 1u8;
        }

        if v != 1 {
            return false;
        }
    }
    true
}

// ----------------------------------------------------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------------------------------------------------
/// 用大整数实现的算法，可以不用担心数据溢出的问题了，支持的数据可以大于u128.
pub fn max_prime_factor_biguint(number: BigUint, save: Rc<RefCell<BigUint>>) -> BigUint {
    if number == 1u8.into() {
        return save.borrow().clone().max(number);
    }

    let fac = pollard_rho_biguint(number.clone());
    if fac == 1u8.into() || fac == number {
        let max = save.borrow().clone().max(fac);
        *save.borrow_mut() = max.clone();
        return max;
    } else {
        let max = max_prime_factor_biguint(fac.clone(), save.clone())
            .max(max_prime_factor_biguint(&number / fac, save.clone()));
        *save.borrow_mut() = max;
    }
    return save.borrow().clone();
}

// 使用pollard_rho算法求因式
pub fn pollard_rho_biguint(number: BigUint) -> BigUint {
    if number == 4u8.into() {
        return 2u8.into();
    }
    if is_prime_biguint(number.clone()) {
        return number;
    }

    loop {
        let c = rand_biguint(&1u8.into(), &(&number - 1u8));
        let mut t = 0u8.into();
        let mut r = 0u8.into();
        let mut p: BigUint = 1u8.into();
        let mut q;
        loop {
            for _ in 0u32..128 {
                t = f_biguint(&t, &c, &number);
                r = f_biguint(&f_biguint(&r, &c, &number), &c, &number);
                if t == r {
                    break;
                }
                q = &p
                    * abs(t.to_bigint().unwrap() - r.to_bigint().unwrap())
                        .to_biguint()
                        .unwrap()
                    % &number;
                if q == 0u8.into() {
                    break;
                }
                p = q;
            }

            let d = gcd(p.clone(), number.clone());
            if d > 1u8.into() {
                return d;
            }
            if t == r {
                break;
            }
        }
    }
}

#[inline(always)]
fn rand_biguint(start: &BigUint, end: &BigUint) -> BigUint {
    let mut rng = rand::thread_rng();
    rng.gen_biguint_range(start, end)
}

#[inline(always)]
fn f_biguint(x: &BigUint, c: &BigUint, number: &BigUint) -> BigUint {
    (x * x + c) % number
}

// 这个函数计算出a^d mod n的值。使用快速幂算法。
// 初始化结果为1，基数为a，指数为d。
// 当指数d大于0时，如果d为奇数，则将结果乘以基数并对n取模。
// 将基数平方并对n取模，将指数整除2。
// 重复上述步骤直到指数d为0。
// 返回a^d mod n
fn fast_power_mod_biguint(mut a: BigUint, mut d: BigUint, n: BigUint) -> BigUint {
    let mut res = BigUint::one();
    while d != 0u8.into() {
        if (&d & BigUint::one()) != 0u8.into() {
            res = &res * &a % &n;
        }
        a = a.pow(2) % &n;
        d >>= 1;
    }
    res
}

// 米勒拉宾素性检验：如果n是一个素数的话，那么n-1可以写成n-1=(a的(2^r)*d次方)*d
// 0<= r <= s-1,a是随机的从[1, n-1]中选取的，如果我们能找到(a^d mod n) != 1 且 (a的(2^r)*d次方) mod n != -1
// 则说明a是n为合数的一个凭证。
// 参数解释:a,d，n分别是公式中的a,d,n
pub fn is_prime_biguint(n: BigUint) -> bool {
    if n < 3u8.into() || &n % 2u8 == 0u8.into() {
        return n == 2u8.into();
    }
    // t保存的是s的值
    let mut t = 0u8.into();
    let mut d = &n - 1u8;
    while &d % 2u8 == 0u32.into() {
        d = &d / 2u8;
        t = t + 1u8;
    }

    for a in A {
        let mut v = fast_power_mod_biguint(a.into(), d.clone(), n.clone());
        if v == 1u8.into() || v == &n - 1u8 || v == 0u8.into() {
            continue;
        }
        let mut i = BigUint::one();
        while i <= t {
            v = &v * &v % &n;
            if v == &n - 1u8 && i != t {
                v = 1u8.into(); // 不需要再循环了。
                break;
            }
            if v == BigUint::one() {
                return false;
            }
            i = i + 1u8;
        }

        if v != BigUint::one() {
            return false;
        }
    }
    true
}
